1. Field of the Invention
The present invention relates primarily to the field of data compression, and in particular to an entropy coding method using adaptive prefix codes.
Portions of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office file or records, but otherwise reserves all rights whatsoever.
2. Background Art
Computer systems are increasingly being used to play back multimedia (audio and video) files. Current computer systems are often unable to transfer data from a file quickly enough from storage to permit adequate playback of a multimedia file. This delay is directly proportional to the amount of data to be transferred.
One way to solve the problem of transmitting a large file is to compress the data for transmission and decompress it back at the destination. However, some compression schemes are not suitable for environments where there is little processing power available (thin clients), or either the compression or decompression schemes are difficult to perform, or require prior knowledge of certain parameters in the schemes.
As mentioned earlier, computers are often used to process, play back, and display video data. This data may come from sources such as storage devices, on-line services, VCRs, cable systems, broadcast television tuners, etc. Video data is not only memory intensive, that is, video data requires large amounts of memory for storage and use by a computer system, but requires the computer system to continuously and uninterruptedly process, play back, and display the data.
To reduce the transmission bandwidth and memory requirements when working with video data, various compression schemes have been developed so that less storage space is needed to store video information and a smaller bandwidth is needed to transmit it. Prior art video compression schemes include Motion JPEG, MPEG-1, MPEG-2, Indeo, QuickTime, True Motion-S, CinePak, etc.
Entropy Coding
Entropy coding is a method of compressing data that is used by video and graphics compression schemes. Entropy coding produces a unique code for each entity of text, audio, video, or graphics data in the file. The length of these code words is based on the probability of the occurrence of the data represented by the code word. Huffman and Golomb coding schemes are two known entropy encoding methods that are extensively used by most present text, audio, video, and graphics compression schemes.
Huffman Coding Scheme
The Huffman coding scheme is perhaps the best and most widely used form of entropy coding. It uses an algorithm known as the xe2x80x9cgreedyxe2x80x9d algorithm to accomplish its task. The greedy algorithm obtains an optimal solution to a problem by making a sequence of choices. For each decision point in the algorithm, the choice that seems best at the moment is chosen. This heuristic strategy does not always produce an optimal solution, but does in most cases. Two ingredients of the Huffman greedy algorithm are the greedy-choice property (a global optimal solution can be derived at by making a locally optimal choice) and optimal substructure (the optimal solution to a problem contains within it optimal solutions to subproblems).
Entropy encoding can be either fixed length or variable length. Consider an example of compressing an alphanumeric file. ASCII coding schemes use 8 bits for each alphanumeric (letter or number) character. Thus, a file that contains 100,000 characters requires 800,000 bits to represent its data. Assume that the file comprises of just six characters, viz. xe2x80x9caxe2x80x9d, xe2x80x9cbxe2x80x9d, xe2x80x9ccxe2x80x9d, xe2x80x9cdxe2x80x9d, xe2x80x9cexe2x80x9d and xe2x80x9cfxe2x80x9d.
Entropy encoding is implemented by determining the frequency of the occurrence of the characters in the file. The table below represents the frequency of occurrence of each character in the example file and proposes a coding solution for fixed length and variable length coding schemes.
Fixed Length Encode
In the fixed length encoding scheme, the maximum number of bits needed to represent the actual number of characters used in the file is determined. If this number of bits is less than the number of bits needed to represent all characters in the alphanumeric set, then compression is possible. For example, with six characters, three bits are needed to encode the six alphabets where xe2x80x9caxe2x80x9d=000, xe2x80x9cbxe2x80x9d=001, xe2x80x9ccxe2x80x9d=010, xe2x80x9cdxe2x80x9d=011, xe2x80x9cexe2x80x9d=100, and xe2x80x9cfxe2x80x9d=101. (By comparison, a file with nine characters needs four bits to encode, and a file with more than 128 characters (but less than 257) needs eight bits to encode). Using this scheme requires 3*100,000=300,000 bits to encode the entire example file. This is a savings of approximately 62.5% (300,000 bits as compared to 800,000 bits) over the uncompressed version. (It must be noted though, that a file with more than 128 characters (but less than 257) will require the same number of bits to store or transmit in both the compressed and uncompressed versions because the codeword for the characters will need 8 bits to encode, meaning no compression is achieved).
Variable Length Encoding
Variable-length coding schemes assign frequent characters short codewords and infrequent characters long codewords. In the example, we have encoded xe2x80x9caxe2x80x9d with a single bit since it is the most frequently occurring character (40,000 occurrences). The next most frequently occurring characters xe2x80x9cbxe2x80x9d, xe2x80x9ccxe2x80x9d, and xe2x80x9cdxe2x80x9d are represented by with two bits, and xe2x80x9cexe2x80x9d and xe2x80x9cfxe2x80x9d with are represented by three bits as the least frequently occurring characters. Using variable length encoding, the scheme requires 156,000 bits (40000*1=10000*2=12000*2=18000*2=5000*3=7000*3) to encode the entire file. This is a savings of approximately 80.5% (156,000 bits as compared to 800,000 bits) over the uncompressed version and significant savings over the fixed length encoding scheme.
Decode
Using either of the above mentioned code schemes, the decoding process occurs as follows: the first bit is received and checked with the table to see if it represents an allowed codeword. If so, the decode process is over. If not, the second bit (if one exists) is received, and the two bits in combination are checked with the table to see if they represent an allowed codeword. As long as an allowed codeword has not been received, the process of receiving new bits and the checking of the ensemble of bits with the table continues, which can be a lengthy and tedious procedure.
Drawbacks With Huffman""s Scheme
There are several drawbacks with the Huffman coding scheme. Firstly, a binary code has to be chosen for the frequency occurrence of characters (alphabets, numbers, punctuation characters, and audio, video, or color entities) for each data file, which will vary from one file to another depending on the frequency of occurrence of the character in the file. This means that the scheme will vary from not only data file to data file, but also if changes are made to the data file in the future. Secondly, in order to calculate the frequency occurrence of characters in a data file, the scheme has to first make a quantitative assessment of the characters, after which it has to go back to the beginning of the data file to assign the chosen binary code for each character. This means that the scheme has to make two passes of the file in order to encodexe2x80x94a time consuming procedure. In order to avoid lengthy encoding computations, like in the case of MPEG and JPEG, fixed Huffman codes are sometimes used which reduces the lengthy procedure to some extent. Thirdly, the decoding process may become difficult to accomplish since the contents of the data file are read by the computer as one long string of 1""s and 0""s and there is no definitive marker to separate the codeword of one character from the next. Further, this decoding process may become difficult to accomplish if the file contains most or all of the known characters. As explained earlier, the scheme has to check one bit at a time in combination with previous bits in the codeword. This means that if the data file contains more characters, the binary codeword chosen gets longer resulting in a tedious checking procedure that not only increases the latency of the scheme, but also increases operational costs. At times, a lookup table is used to check more than one bit at a time, and this reduces the checking procedure time to some extent. Fourthly, the table, like the one shown in Table 1, will not only become large, but each character has to be checked with all the entries in the tablexe2x80x94a time consuming process. This means that even though the Huffman""s scheme is a good compression scheme, decoding is time consuming and tedious, especially for thin clients that have little computing power, minimal memory, and very little time to decode the compression scheme.
Golomb Coding Scheme
In order to simplify the decoding process of the Huffman scheme, a prior art scheme known as the Golomb scheme produces codewords that are simpler to decode. The encode and decoding procedures using the Golomb scheme are explained below.
Encode
Given a non-integer xe2x80x9caxe2x80x9d and a code base xe2x80x9cbxe2x80x9d, the Golomb code is constructed by first dividing xe2x80x9caxe2x80x9d by xe2x80x9cbxe2x80x9d to obtain a quotient xe2x80x9cqxe2x80x9d, and a remainder xe2x80x9crxe2x80x9d. The base xe2x80x9cbxe2x80x9d is the base system from which a legal non-integer xe2x80x9caxe2x80x9d is chosen. Thus, non-integers 0 through 9 can be chosen for a 10 (decimal) base system, and non-integers 0 through 9, and letters A through F can be chosen for a 16 (hexadecimal) base system. The quotient xe2x80x9cqxe2x80x9d is then represented using a unary representation, which is the number of zeros equal to the quotient xe2x80x9cqxe2x80x9d followed by a one. So, for example, the unary of 1=01, and the unary of 5=000001. This unary representation is post-catenated by the binary representation of the remainder xe2x80x9crxe2x80x9d to form the Golomb codeword Gb(a). For example, if non-integer xe2x80x9caxe2x80x9d=15 is chosen from a code base xe2x80x9cbxe2x80x9d=7, then xe2x80x9cqxe2x80x9d=2 and xe2x80x9crxe2x80x9d=1. Since the unary representation of xe2x80x9cqxe2x80x9d=001 and the binary representation of xe2x80x9crxe2x80x9d=01, the Golomb code word G7(15)=00101.
Decode
In order to decode this codeword, the number of zero bits left of the first one bit are counted to give the value of xe2x80x9cqxe2x80x9d. In our example, since there are two zero bits left of the first one bit, xe2x80x9cqxe2x80x9d=2. The first one bit is then discarded, and the remaining bits are converted from the binary system to the base system to yield xe2x80x9crxe2x80x9d=1. The original integer xe2x80x9caxe2x80x9d is reconstructed as: a=b*q+r=7*2+1=15.
Drawbacks With Golomb""s Scheme
There are several drawbacks with this scheme. One problem is that the code base xe2x80x9cbxe2x80x9d has to be known by the computer prior to decoding the data file. Since there are several kinds of popular operating systems, and a plethora of sources for data files, the knowledge of the base code xe2x80x9cbxe2x80x9d limits the scope of this scheme. Moreover, the choice of the code base xe2x80x9cbxe2x80x9d influences the efficiency of data compression. For a given non-integer xe2x80x9caxe2x80x9d, a small value for the code base xe2x80x9cbxe2x80x9d produces a large value for quotient xe2x80x9cqxe2x80x9d, which equates to a long unary representation of xe2x80x9cqxe2x80x9d and a small value for remainder xe2x80x9crxe2x80x9d, which equates to a short binary representation of xe2x80x9crxe2x80x9d, while on the other hand a large value for the code base xe2x80x9cbxe2x80x9d for the same non-integer xe2x80x9caxe2x80x9d produces the opposite results. Since finding the optimal value for the code base xe2x80x9cbxe2x80x9d for a given set of data is computationally difficult, the chances of getting an efficient compression scheme as opposed to an inefficient one is equally possible.
Even though the Golomb scheme like the Huffman scheme has no definitive markers to separate the codeword of one character from another, it is easier to decode a data file using the Golomb scheme because it uses the same algorithm to encode each character irrespective of its frequency in the data file. Hence, the codeword for each character is the same for all data files irrespective of size, kind, or changes made to them as long as the base code xe2x80x9cbxe2x80x9d is known and remains unchanged. As mentioned earlier, since code base xe2x80x9cbxe2x80x9d has to be known by the computer prior to decoding, this scheme is not universally accepted and loses its advantage over Huffman""s scheme.
The present invention provides an entropy coding scheme using an adaptable prefix code. The prefix code is a binary representation of the algorithm used to compress and decompress the data. There are prefix zeros that represent the number of binary digits that follow the first one. For example, the entropy codeword for 14 is 000011110 because the sequence of bits following the first one (1110) is the binary representation of 14, and its length equals the number of prefix zeros before the first one bit. According to one embodiment, this scheme works on both positive and negative integers. In another embodiment, the zero integer is handled as a special case and is assigned the shortest codeword. In yet another embodiment, since the present scheme uses the shortest codeword for the zero integer, it is preferred by data sets that are clustered about zero, such as image data sets that have been transformed via a wavelet transform or a discrete cosine transform.
Since many modem computer instruction set architectures include an instruction that can count the number of leading zeros in a word, the present scheme in another embodiment makes use of this instruction in the encoding and decoding of the data file.